1. Field of the Invention
The present invention relates to a method and a device for tracking the path of motion of a moving object according to the preamble of claim 1. It further relates to a computer program that implements this method as well as to a data storage medium with a computer program of this type.
2. Discussion of Background Information
Methods of this type, which are referred to in general as “tracking” methods, are generally known and are described, for example, in the literature reference Zhang, H.; Laneuville, D.: Grid Based Solution of Zakai Equation with Adaptive Local Refinement for Bearings-only Tracking, IEEE Aerospace Conference 2008, pages 1 through 8. Such known methods are used, for example, to be able to determine the path of motion of missiles with a relatively high degree of accuracy and to predict the movement of the missile even if only few and possibly faulty localizations of the missile are available. Localizations of this type can be carried out, for example, by radar measurements by one or more measuring devices.
Using all available measurement data from such localizations of the object up to a current point in time, first of all the current position of the object must be determined. As far as possible this should be carried out in real time or quasi-real time, since it is necessary, for example, for engagement of an approaching missile, to know at least the current position of the missile and possibly even to predict the further path of motion of the missile.
In addition to the position of the object, for example, of a missile, as a rule other state variables, such as, for example, the speed vector or parameters of maneuver models, like the ballistic coefficient, are also of interest, since an approaching missile does not move along a linear path of motion at uniform speed, but in general is controlled such that it flies tactical maneuvers.
Furthermore, it can also be necessary to determine estimates of the state variables (including the position data) of the object for past points in time (so-called smoothing) or for future points in time (so-called prediction). It can also be desirable to be able to process measurements that are not available until later, that is, not in real time (so-called latency times).
If the object described a linear movement or if the state variables of the object changed in a linear manner, with normally distributed start distribution and normally distributed measurement errors, a calculation could be made with relatively little expenditure by Kalman filters. However, in practice, the states of the object change in a non-linear manner. For example, in a diversionary maneuver a missile can slow down, accelerate or abruptly change direction, so that determining a path with a Kalman filter is not possible or possible only very inaccurately. Accordingly, if, as in practice, the movements and other state variables of the moving object of interest are to be described by non-linear equations, an optimum determination of the estimate in a closed form is often not possible.
The problem can now be described in the form of stochastic differential equations for the in general multi-dimensional system state variable Xt, and the in general multi-dimensional measurement Yt dXt=f(t,Xt)dt+σ(t,Xt)dWt dYt=g(t,Xt)dt+ν(t,Xt)dVt f, g, σ, ν are thereby suitable functions and W and V are two Brownian motions, which illustrate the noise of the system and measurement respectively. Xt thereby describes the complete state of the motion at the point in time t, thus contains, for example, the position and the speed at the point in time t.
Analogously the system can also be described discretely at points in time tk Xk+1=f(tk,Xk)+σ(tk,Xk)Wk Yk+1=g(tk,Xk)+ν(tk,Xk)Vk with normally distributed random variables Wk and Vk.
A number of approximation methods for non-linear filter problems are known.
Extended Kalman filters and other linearizing methods linearize the system equations and solve the linearized problem. Depending on the degree of the nonlinearities in the system, marked inaccuracies up to divergence of the filter are unavoidable.
Sampling methods such as particle filters or unscented filters consider the behavior of the system for a few suitable state vectors x, which are selected either randomly or systematically. Since realistic problems require, for example, five-dimensional to ten-dimensional state vectors, the use of some fewer system state vectors in higher dimensions leads to high inaccuracies.
An exact treatment of the problem takes place, for example, by considering the conditional density function
            p      t        ⁡          (      x      )        :=            ∂              ∂        x              ⁢          P      ⁡              (                                                            X                t                            ≤              x                        |                          Y              s                                ,                      s            ≤            t                          )            P(Xt≦x|Ys,s≦t) is thereby the probability that the unknown random state vector at the point in time t will adopt a value smaller than or equal to x, with given measurements up to the point in time t.
It is known that the conditional density function pt contains the complete information on the movement of the object at the time t. The optimum estimate t of the system state (in the sense of the minimization of the error variance) is produced, for example, as a conditional expectation, that is, by integration of the density function,t=∫xpt(x)dx 
The exact determination of this density function thus solves the problem exactly. In the continuous case it can be shown that the density function fulfills the stochastic partial differential equation
      ∂          p      t        =                                                        [                                                -                                                            ∑                      k                                        ⁢                                                                  ∂                                                  ∂                                                      x                            k                                                                                              ⁢                                              (                                                                                                            f                              k                                                        ⁡                                                          (                                                              t                                ,                                x                                                            )                                                                                ⁢                                                                                    p                              t                                                        ⁡                                                          (                              x                              )                                                                                                      )                                                                                            +                                                                                                                          1                  2                                ⁢                                                      ∑                                          i                      ,                      k                                                        ⁢                                                                                    ∂                        2                                                                                              ∂                                                      x                            i                                                                          ⁢                                                  ∂                                                      x                            k                                                                                                                ⁢                                          (                                                                                                    b                            ik                                                    ⁡                                                      (                                                          t                              ,                              x                                                        )                                                                          ⁢                                                                              p                            t                                                    ⁡                                                      (                            x                            )                                                                                              )                                                                                  ]                                          ⁢      dt        +                                                      [                                                                    g                    ⁡                                          (                                              t                        ,                        x                                            )                                                        ⁢                                                            p                      t                                        ⁡                                          (                      x                      )                                                                      -                                                                                                                                              π                    t                                    ⁡                                      (                                          g                      ⁡                                              (                                                  t                          ,                                                      X                            t                                                                          )                                                              )                                                  ⁢                                                      p                    t                                    ⁡                                      (                    x                    )                                                              ]                                          ⁢                        d          ⁢                      W            ~                                    υ          ⁡                      (                          t              ,              x                        )                              where b(t,x):=σ(t,x)σ(t,x)T·πt(g(t, Xt)) is thereby the estimate of the variable g(t, Xt) and {tilde over (W)} the innovation process, equations of this type are also referred to as Zakai equations.
The component
  -            ∑      k        ⁢                  ∂                  ∂                      x            k                              ⁢              (                                            f              k                        ⁡                          (                              t                ,                x                            )                                ⁢                                    p              t                        ⁡                          (              x              )                                      )            determines the “shift” of the density function and is referred to as the advection term, the term
      1    2    ⁢            ∑              i        ,        k              ⁢                            ∂          2                                      ∂                          x              i                                ⁢                      ∂                          x              k                                          ⁢              (                                            b              ik                        ⁡                          (                              t                ,                x                            )                                ⁢                                    p              t                        ⁡                          (              x              )                                      )            determines the “expansion” of the density function and is called the diffusion term. These two components are used to predict the system behavior without the use of measurements. The associated equation
      ∂          p      t        =            [                        -                                    ∑              k                        ⁢                                          ∂                                  ∂                                      x                    k                                                              ⁢                              (                                                                            f                      k                                        ⁡                                          (                                              t                        ,                        x                                            )                                                        ⁢                                                            p                      t                                        ⁡                                          (                      x                      )                                                                      )                                                    +                              1            2                    ⁢                                    ∑                              i                ,                k                                      ⁢                                                            ∂                  2                                                                      ∂                                          x                      i                                                        ⁢                                      ∂                                          x                      k                                                                                  ⁢                              (                                                                            b                      ik                                        ⁡                                          (                                              t                        ,                        x                                            )                                                        ⁢                                                            p                      t                                        ⁡                                          (                      x                      )                                                                      )                                                        ]        ⁢    dt  is called the Fokker-Planck equation.
The last term of the stochastic partial differential equation (measurement term) describes the information gained by the use of measurements. In the discrete case, that is, in the case that measurements are available only at discrete points in time, this part of the equation corresponds to Bayes' formula. Analogous formulas thus also exist in the discrete (that is, the measurement and/or the system itself is considered only at discrete points in time) as well as in the prediction problem or in the smoothing problem.
Zhang and Laneuville (Zhang, H.; Laneuville, D.: Grid Based Solution of Zakai Equation with Adaptive Local Refinement for Bearings-only Tracking. IEEE Aerospace Conference 2008, p. 1-8) solve an equation of this type by numerical methods. To this end, the function pt is represented on a locally refined regular grid of nodes and the equation is discretized. Problems up to four dimensions can be processed in this manner. Since the expenditure increases exponentially with the number of dimensions, an application to higher dimensions is possible only with difficulty.
In recent years, as a new approach, so-called “sparse grids” have been introduced for the interpolation of higher-dimensional functions by Zenger [Zenger, C.: Sparse Grids, in W. Hackbusch (ed.): Parallel Algorithms for Partial Differential Equations. Braunschweig: Vieweg, 1991 (Notes on Numerical Fluid Mechanics 31), pages 241 to 251]. In DE 100 62 120 A 1 this approach is described in the field of financial mathematics for the valuation of financial derivatives. These grids require in d-dimensional space O(N(log N)d-1) points, that is, substantially less than a regular grid with O(Nd) points.